{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 1. Self-Balancing Search Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We looked at Search Trees previously, and we knew that they were better if balanced. Now we explore how to automatically keep them balanced."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.1 Tree Balance and Rotation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Most of the algorithms that we will discuss use the ideas of balance and rotation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.2 AVL Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have explored AVL trees very thoroughly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.3 Red-Black Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rules (Invariants):\n",
    "\n",
    "<img src=\"red-black-algo.png\"/>\n",
    "\n",
    "Adding a new node:\n",
    "\n",
    "* initial color is red\n",
    "* if parent is black, you are done\n",
    "* else if parent is red, and *parent has a red sibling*\n",
    "  * change grandparent to red\n",
    "  * change parent/sibling to black\n",
    "  * if root is red, change to black\n",
    "* else parent is read, but no red sibling\n",
    "  * grandparent to red\n",
    "  * parent black\n",
    "  * rotate around grandparent\n",
    "\n",
    "<img src=\"fig-9-22.png\"/>\n",
    "\n",
    "Fig 9.22:\n",
    "\n",
    "1. insert 35\n",
    "2. 30 and 10 are red, so:\n",
    "3. change 10, 30, 20\n",
    "4. done\n",
    "\n",
    "Fig 9.23:\n",
    "\n",
    "1. insert 35\n",
    "2. change 20 and 30\n",
    "3. rotate grandparent left\n",
    "4. done\n",
    "\n",
    "<img src=\"fig-25.png\"/>\n",
    "\n",
    "Fig 9.25:\n",
    "\n",
    "1. insert 25\n",
    "2. rotate parent to right \n",
    "3. rotate grandparent to left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "format": "tab"
   },
   "outputs": [
    {
     "data": {
      "image/jpeg": "/9j/4AAQSkZJRgABAQAAAQABAAD/2wCEAAUDBAgICAgICAgJCAgGCAgIBwcHBwgICAgICAgICAgI\nCAgIDhALCAgPCQgIDRUNDhERExMTCAsWGBYSGBASExIBBQUFBwYHDwgIDx8VEhQeHhwfHhscHR4e\nHhwZHhscHBwbGBocHhodHB0cHR4fGhsfHR8eHB0cGxweGB4cHRwUHf/AABEIAWgB4AMBIgACEQED\nEQH/xAAdAAEAAgIDAQEAAAAAAAAAAAAABQgEBwEDBgkC/8QARhAAAQMCAwEMCQMCBAUFAQAAAQAC\nAwQFBhESIQcTFBgxQVFSVJKU1AgVIjIzcZGx4SNhckKBFiWh0QkkYoLBNENE8PEm/8QAHAEBAAID\nAQEBAAAAAAAAAAAAAAUGBAcIAwIB/8QAMBEBAAEDAgQEBQMFAQAAAAAAAAECAxEEBRIhMVEGQXGR\nBzJhgaETIkKxwdHh8HL/2gAMAwEAAhEDEQA/AKZIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiA\niIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiI\nCIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiI\ngIiICIiAiIgIrMcSvFPb7H4y4+TTiV4p7fY/GXHyaCs6KzHErxT2+x+MuPk04leKe32Pxlx8mgrO\nisxxK8U9vsfjLj5NOJXint9j8ZcfJoKzorMcSvFPb7H4y4+TTiV4p7fY/GXHyaCs6KzHErxT2+x+\nMuPk04leKe32Pxlx8mgrOisxxK8U9vsfjLj5NOJXint9j8ZcfJoKzorMcSvFPb7H4y4+TTiV4p7f\nY/GXHyaCs6KzHErxT2+x+MuPk04leKe32Pxlx8mgrOisxxK8U9vsfjLj5NOJXint9j8ZcfJoKzor\nMcSvFPb7H4y4+TTiV4p7fY/GXHyaCs6KzHErxT2+x+MuPk04leKe32Pxlx8mgrOisxxK8U9vsfjL\nj5NOJXint9j8ZcfJoKzorMcSvFPb7H4y4+TTiV4p7fY/GXHyaCs6KzHErxT2+x+MuPk04leKe32P\nxlx8mgrOi3nffRfv9Lc7fZxWWqquF1Ekraekqa1/BaOHIS19a6SmYIKQPLWA7XPc7JjXEHL0vErx\nT2+x+MuPk0FZ0VmOJXint9j8ZcfJpxK8U9vsfjLj5NBWdFZjiV4p7fY/GXHyacSvFPb7H4y4+TQV\nnRWY4leKe32Pxlx8mnErxT2+x+MuPk0FZ0VmOJXint9j8ZcfJpxK8U9vsfjLj5NBWdFZjiV4p7fY\n/GXHyacSvFPb7H4y4+TQVnRWY4leKe32Pxlx8mnErxT2+x+MuPk0FZ0VmOJXint9j8ZcfJpxK8U9\nvsfjLj5NBWdFZjiV4p7fY/GXHyacSvFPb7H4y4+TQVnRWY4leKe32Pxlx8mnErxT2+x+MuPk0FZ0\nVmOJXint9j8ZcfJpxK8U9vsfjLj5NBWdFZjiV4p7fY/GXHyacSvFPb7H4y4+TQVnRWY4leKe32Px\nlx8mnErxT2+x+MuPk0FZ0VmOJXint9j8ZcfJpxK8U9vsfjLj5NBWdFZjiV4p7fY/GXHyacSvFPb7\nH4y4+TQVnRWY4leKe32Pxlx8mnErxT2+x+MuPk0F/URcO5EHKKG35/Xd3im/P67u8UEyiht+f13d\n4pvz+u7vFBMoobfn9d3eKb8/ru7xQTKKG35/Xd3im/P67u8UEyiht+f13d4pvz+u7vFBMoobfn9d\n3eKb8/ru7xQTKKG35/Xd3im/P67u8UEyiht+f13d4pvz+u7vFBMoobfn9d3eKb8/ru7xQTKKG35/\nXd3im/P67u8UGsfSx3ZHYRtkJpGMkul3fLFQCZpdFCyFrDUVT2j3yzfYg1hORdICcw0g0oovSLxp\nFUip9e1Mjg8OdDMyB9M/bmWGn0b2GHaPZAy5stisp6d2Aa+726guVEySpdYXVXCqaNrpJTTVQgLp\n42jMuEbqcagB7shPI0qi8MbnuaxjS98jg1jGAuc5zjk1rWjaXEkDIdKD6nejzumR4rscNzEYgqI5\nH0twp2aiyKriax796LtpidHJFI3MkgSZEktJWxFoH0PsDVuH8OCKuD4aq6VclwlpXZtfTNkhghii\nkHNLogD3A7QZNJ2tK3Lvz+u7vFBMrzG6XjKGyUJqXxvqamokZS2y3QZGouFfNmKelgb0k5lzv6WM\ne48i/V7vUVDTT1lXUbxTUcT5qieR5DY42DNzj0nmAG0kgDaVr3c5ttVd61uKrtFJC/e3xYZtlQc3\n2u3yjJ9ZKM8m3KqZk53PHGWsz2kAPXbkuDZ7fHUV9zkZU3++vbUXeqjz3qMtBEFuotW1lBTtJYwE\nkk63Ha7Z7lQ2/v67u8U35/Xd3igmUUNvz+u7vFN+f13d4oJlFDb8/ru7xTfn9d3eKCZRQ2/P67u8\nU35/Xd3igmUUNvz+u7vFN+f13d4oJlFDb8/ru7xTfn9d3eKCZRQ2/P67u8U35/Xd3igmUUNvz+u7\nvFN+f13d4oJlFDb8/ru7xTfn9d3eKCZRQ2/P67u8U35/Xd3igmUUNvz+u7vFN+f13d4oJlFDb8/r\nu7xTfn9d3eKCZRQ2/P67u8U35/Xd3igmUUNvz+u7vFN+f13d4oJlFDb8/ru7xTfn9d3eKCZRdVGS\nWNJOZyO0nM8pXagLh3IVyuHchQQaIiAiy6WkD26tWW0jLLPkXb6vHXPd/KCPRSHq8dc938p6vHXP\nd/KCPRSHq8dc938p6vHXPd/KCPRSHq8dc938p6vHXPd/KCPRSHq8dc938p6vHXPd/KCPRSHq8dc9\n38p6vHXPd/KCPRSHq8dc938p6vHWPd/KCPRSHq8dY938p6vHXPd/KCPXmN0PH9nw/AKi7V0dK1/w\nojqkqJzmBlBTxgySDMjMgZDnIC8x6SW6rHhemhpqNrau+XUO9X0bgTHDGDpfW1WR2QNOYDcxrcDz\nNeRUB9JPU1L7hcqmS4XKoOuarqDrLSczogafZiibmQGtAAGwADIDC1mvt6WP3c57LR4b8Ka3f7k/\npftojrVPT0jvP095hvS9+lXI92Vnw9PLHt01N1qmUee0ZOFPEHlzSM9u+dC8zS+kFdo6h1SMK2QS\nkkiaF+91P751G0uccztyHKteb3+6b3+6g6t8vTPKIbTs/CzbaaMXK65nvmmPxif6t+4V9Km2ve2O\n92yssxecuFMIuFE3bs1ywtbK3PobG7/yt82O60tdBHVUVRFVU04ziqKaRssTxz5PYcsxzjlHOqEO\nhBBB2g7CCMwR0Ec4WFT1NxtEdV6oqaiGluDN7utsppt7ZV05yEwgJa7g9QYw5gkY3UA46eq7O0m8\n0XKuC7GJ7+SreIPhpqNFanUaGqa6Y60z82PpjlPpiJ7ZW3ZljC4h+12FsP1R0DaI7/d6Z2Ws809p\nppAcv6ZJmf1Bi20SvPbjF2tN2sdBV2XKG3iFsEVJoDX0boAGPpJWZ7JGEZE7Q7MOBcHBx9h6vHXP\nd/Km2rUeikPVw6x7v5T1eOse7+UEeikPV4657v5T1eOue7+UEeikPV4657v5T1eOue7+UEeikPV4\n657v5T1eOue7+UEeikPV4657v5T1eOue7+UEeikPV4657v5T1eOue7+UEeikPV4657v5T1eOue7+\nUEeikPV4657v5T1eOue7+UEeikPV4657v5T1eOue7+UEeikPV4657v5T1eOue7+UEeikPV4657v5\nT1eOue7+UEeikPV4657v5T1eOue7+UEeikPV4657v5T1eOue7+UEeikPV4657v5X5koQGk6vdBPJ\n0DPpQYKIiCXofht+R+5Xcumh+G35H7ldyAuHchXK4dyFBBoiIJS2/DHzKyVjW34Y+ZWSgIiICIiA\niIgIiICIgQcgLFuNc2EZZZuPI39ukpca0RDIbXuGYHNl0lRDY9Ts3u94+07lQTVBVCZmoDI/1DoP\n/wBC67xcIaOnqKuoeI6eiglqKiV2xscMEbpZXk9AY1x/svxFXQRtDWnIN/b/AFP7rVfpe3/eME3y\nSB3tTxU9IeQEMq6uCnlG3lzhfIP7oKhXLEE99uVdf6vPfbrK7gsTtvBaCM6KanYP6QGNaTlscfa5\nSc/2umjgEUccbfdiY1jfk1oA+y7lQtTfm/dqrnzdb7HtdvatBa0tEfLHP6z5z95EVmtwy+cPp6Sj\ntmHKJlJRvihvlXVzwySSNfHkZ2+wHyzuDHOIc0j3WjIe03AwLhuy/wCIMUXGKmZUUGG49+paRzP0\nRUmKSSfQx4yyZLTVDWAgtbqaQPZasqNv4opmmr5vpPbM+uEBc8Y/oXL9u/YmJtRnlVTOc1RTTE4+\nWapmJiJmeXNXRFvrG1VSYjwlU311BBRXCzVrKZz6RgYJYnyUzN7J5XR6axhydtDo3ZZBxB0KsXUW\nP0pjE5iYzCf2jdJ3C3XNdHBVRVNFUZziYxPKY6xiYe+9FTF7rJiZtue8i24vzjEZP6cF1ibqgkaC\ncm763OI5DNzpI+Zgyu8AvmZiitdSMp6+P41praStgPJ+rDOwt28239ivpVNcImacz77Q8ZDP2TyH\n/RWvar83tNGescnPvxA2u3t29VxbjFNcRXjtnMT+YmXVc7iIS1obqJ5f2Gz/AHWVSztlaHN/uOcf\nNYVZPBMACciMy12W0Z/+OT6BYFNI6J2pu3mI5iFJKUnyEX5pp2yN1N//AA9C/SAiIgIiICIiAiIg\nIiICIiAiIgIiICIiAiIgIiIC66j3H/xd9iuxddR7j/4u+xQQyIiCXofht+R+5Xcumh+G35H7ldyA\nuHchXK4dyFBBoiIJS2/DHzKyVjW34Y+ZWSgIiICIiAiIgIiIC5C4RBH3eiLnCVu0tbpLekAkjL6l\nYEJa4gOOkHYTlyfNehaVF3a3E+3ENv8AUwbM/wB9uzNBw60Z8knL/wBP5Wo/TDsT3YHvQZ+o6I0V\nSQAdjIK6nMjhl0Raz/Yrc1pikZEBIduWxp26Rt9nP6fRY2K7LDc6Ctt1SCYLnSz0k2XKI6iJ0Ti0\n8zgHZg8xAQfPOCQPY17drXta5p6Q4Aj/AEK/aw6S3VFunq7NWjTWWKd9JMCMtcbTnBMwHlifFpLT\nzgg86zFQNRamzcmifJ13tG4W9y0VvVW+lcRPpPnH2nksBgKvwbFHb66K5VtlqqB0U9woWTVbxVyx\nlp0P9lzZ4S5jxlHkSyUhwaSMsfD26vaziK+zVTJIrRiWFlM+QRuMjN4pxTtlfHFm4NkaZidIc4GV\nvQVodFkxuFcRTFMRGOfTryx/RCVeD9Lcqu1XrldfHHDzqiZpjiirlOM5iqIxNWcYiG6t0DEVitmH\npcPWOqkuBuNW2prap7XBrAx0MgycWta5x4PTtAYMgGPJIJyOlURY9+/N6qJmMY5REdk1tW129ttV\nUU1TVNUzVVVV1mqcc5xER0iIjEdIQmNKd89M2ljGqauqKamp2deWSZmho5yTlzL6TVdp1lml2kRx\ntjAyz2Nzy+/+ipB6O2FTfsWUYLdVDhUtudc/Tmw1YP8Al8GfJr30b5z5iGUcyvgCrXtFmbemjPnz\nc/8AxF3G3rd7qi3OYtxFH3jMz7TMx9kUbWGDN0uQH/T+VhjNxDWgknkH7dJWdfKaZ5Zozc0E5sBA\nyOz2jny86yrbRiIZnIvI9p3+uQz5B/sFJqK5t1IIWkZ5lxzcebPLLZ+y71ySuEBERAREQEREBERA\nREQEREBERAREQEREBERAREQF11HuP/i77Fdi66j3H/xd9ighkREEvQ/Db8j9yu5dND8NvyP3K7kB\ncO5CuVw7kKCDREQSlt+GPmVkrGtvwx8yslAREQEREBERAREQEREBc5rhEHJK4REGgPSr3GJ7xvd9\nsrG+u7fFvU9Nm1rbpRt9reSTs4Sz+hxIzHsk7GZVVtVzZPrYWuiqKdzo6mkmaY54JWHS+OSNwDgQ\n4EcnKCNhBAvlus4zmtsUFHbomVV+vj3U9mon5mMSBuctdV6faZb6dpD5HD/paNrsx4W9+jNY6+hh\nbWTVRvbN8mqcS08u919VWTu3yeWZpzjkhLzpbGRmxgDWubtJjtdt1GqjPSrv/lcvCnjLU7BVNvHH\nanrT2nvTPlPfyn8qqotm3/0aMW0bjwGutl4gb7pqN9oKt37aMnQjZzmQ8hUDBuIY8c9zDZ6KMNOT\nZpLtSmN/7tEby/L5tB2KAq2bVROIiJ+7bln4l7Fco4qqqqZ7TTP9sx+XkFi0EdXc66GzWaIVVzrC\nWtGYENKwDOSoqJD7LGMbm4g58nISWtduvCnoq3iqcDfr1DSQZ+3SWFj3zSN6OGVTRvLs+hkgyW5a\nzcMs9PaY6KxxNtFdbpm11ru0Wb6uK4RNIZLUzPzfUwPBdHJE72XRyOaANmWfpNl4auK/P2/yqfiL\n4nxdtTY2umYz/OrlMf8AmO/1np280zuGbmlNha0x2+F2/wBRK41FyrnNyfV1kmW+SHnbE3Y1jeZr\nRnmS4n3i8XuVY2N2hnpqyJtHe7LI2mvdtzP6M5bmyppw46pKCdv6kUm0FpyzJaV7RWFp6ZmZzLnN\nCVwiPwREQEREBERAREQEREBERAREQEREBERAREQEREBERAXXUe4/+LvsV2LrqPcf/F32KCGREQS9\nD8NvyP3K7l00Pw2/I/cruQFw7kK5XDuQoINERBKW34Y+ZWSsa2/DHzKyUBERAREQEREBERAREQER\nEBQWPcVUllt89xrC7e6cARwxjXPUzyHRBS00Y2y1EkhaxrRzuzOQBImKypjhjkmme2KGnY+WaWRw\nayOONpe973HY1gaCSTyALVGBaaTFNxhxNWMeyz24v/wlb5muZvzjmyTEFVC8bZZBmKcH3I3F+QLw\nUExuS4Tqmy1GIb2xvr+9xta6EESMs1uB109npnjYQ05Ple3LfJSSc9LStiIiAiIgIiINd7q+FKsy\nw4hsTGevrRG5hp3O3qK9W8nXNaqp45zkXwvdmI5QOQOJHpsA4rpL3QQ3CjLhHNmyWCZoZUUlRGdM\n9JVRZ5w1Mb82uaejMZggmeWpceW+fDdxlxRbmPkttWG/4ttELNWpjNjb9Rxt28NhZslaPixNz95m\nZDbSLGtdfBVwQ1VNKyenq4mTU88Tg6OWKRoeyRjhsLS0g/3WSgIiICIiAiIgIiICIiAiIgIiICIi\nAiIgIiICIiAiIgLrqPcf/F32K7F11HuP/i77FBDIiIJeh+G35H7ldy6aH4bfkfuV3IC4dyFcrh3I\nUEGiIglLb8MfMrJWNbfhj5lZKAiIgIiICIiAiIgIiICIta7q2JKyoqocM2OTRc7lHvtyuLDmLFaS\nS2SscR/86TbHBHzuzeSAzMhFYkkdi+5yWeB2eGrHOG4iqWHZdrhCQ9ljheP/AI0TtEk7xnmdMWz2\nituxsa1rWsaGtYA1rWgBrWgZBrQNgAGzJRWDMNUdnoKa22+EQUlDGI4oxynaXPkkd/XK95c9zztc\n57ieVS6AiIgIiICIiAh6DtB5QiINN0pGCLhHTaS3CN/qtFK9rf0sOXWqkz4O8DbHaaqZ7i12WiGQ\nkHS14K3IVhX21U1dSz0VZCyopa2J8FRBIM2yRyNLXNOW0bDyjIg5EZELW+5xdaqx1zMK3eZ00cjX\nvwpd5j7VfRRDU+21J5PWVKzSNWecsYa7IEOzDaqIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgI\niIC66j3H/wAXfYrsXXUe4/8Ai77FBDIiIJeh+G35H7ldy6aH4bfkfuV3IC4dyFcrh3IUEGiIglLb\n8MfMrJWNbfhj5lZKAiIgIiICIiAiIgIiicY4jo7RQ1Nyr5RDS0Me+Sv5XEkhsccbeWSZ73NY1g2u\nc9oHKghN1fG4s1NC2CA1t1u84orJbGZ6quseM83kfCpIm5ySyuyaxjeXMtzblGCPU1LM6onNbdrt\nMa293N+eurrHgDJgPwqSJgEUUTcmsYwZAEuzhdyfDdbUVU+J74wsud0jEVstrh7NitBOuKjAO3h8\nubX1D89rg1oDQ3I7LQEREBERAREQEREBERAXm90jBtLfaB9DUl8ZD2VFHWQHTU0NbAddNW0zxtZP\nG/aOkFzTscQvSIg8BuUYxqal9TZbw1sOILG1vCwxuiG5Ujjpp7xRDIA00uWTmj4cgcwgbM/frw26\n1gye4x09fa5WUl/sjnTWiskBMUmrLf7fWhvtSUE7AWOA2tJa8bW5GQ3MsZxXui38ROpKykkdS3W2\nTEcIt9dFsmp5QPebn7TH8j2Oa4cuQD1KIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgLrqPcf8A\nxd9iuxddR7j/AOLvsUEMiIgl6H4bfkfuV3Lpofht+R+5XcgLh3IVyuHchQQaIiCUtvwx8yslY1t+\nGPmVkoCIiAiIgIiICIiD8yPa1rnPcGtYC5znENa1oGZc4nYAAM81qLDkbsX3OO8Tt/8A5qxzk4dp\npG+zdrhESx19la7L/lojrZAwg5kOl2eyF+sd1MmKbjNhijfIyz24tOLrhC90e/FwD48P0szNplkG\nTqgty0RkMzDn5LbFHTRwxxwwsbFDAxkUMUbQyOONjQ1jGMbsawNAAA5AEHaiIgIiICIiAiIgIiIC\nIiAiIgLWG6dh6qt1b/iuyQulrKeFsV+tMIP+eWyLN36cTfiXeBuowv5XAuj2hwC2eiCKwhiKju9D\nTXK3ztqKOvjEsErDyjMhzHjlZKx4cxzDta5jgciCpVagxFHJg+4vu1Owuwzep9WIKSME+pq6Uhrb\n1TRNGQopHZCoaNrSWyDP2gNuwyNe1r2Oa9kjQ5j2ODmua4Ztc1w2OaQQQR0oP0iIgIiICIiAiIgI\niICIiAiIgIiICIiAiIgLrqPcf/F32K7F11HuP/i77FBDIiIJeh+G35H7ldy6aH4bfkfuV3IC4dyF\ncrh3IUEGiIglLb8MfMrJWNbfhj5lZKAiIgIiICIiAtd7rOK6pssGH7I9vr69xuc2ctEjLPbwdFRe\nKlh2HRnpijdlvkhA2hrgpvdOxlHZKHf96dV1lVIyltVthI3+4V82yGniB5Bnm5z+RjGPdzZHC3Js\nGy22KesuMjKq/Xx7Ki81rMzGJA3KKhpNXtMoKdpMcbTy+047XHIJnAWFaSy2+C3UYdvVOHF8srtc\n9TPI4vnqqiQ7ZJ5JC57nHnOQyAAE6iICIiAiIgIiICIiAiIgIiICIiAiIg66mBksb4pWNkimY6OW\nKRoeySN4LXse12xzS0kEHlBWpMIzvwjcIbDVyvfYLvM5uF66d+r1fUPzccPVMrtu97C6me/aRnHm\nS1q2+ojGWG6O8UNRbq+ITUtYzTI3PS5pBDo5YnjbHMx7Wva8bQ5oKCXRa03LcS1lNVy4YvshkudB\nEZrZc3gNbfrW06W1bctja+L2WTRZ555PGbXZjZaAiIgIiICIiAiIgIiICIiAiIgIiICIiAuuo9x/\n8XfYrsXXUe4/+LvsUEMiIgl6H4bfkfuV3Lpofht+R+5XcgLh3IVyuHchQQaIiCUtvwx8yslY1t+G\nPmVkoIfGmI6a00NRcKskQ0rQS1gBkke5wZHFGDkC9z3AbcgM8zkASq41fpL3Qz6oqCiZTatkEm/y\nTFme0Gdr2t15c4ZkOgraPpT2ierw9I6AF3AKmGrnY3aTAxkschy5w3fQ89AYTzKnKru762/auxRR\nOIw3L8PPDO1bht9ep1VEV18Uxif4xER5d5659vNe/crx1TYgoBWQMMMkb96qqZ7tToJg0OyD8hvk\nZDgQ/IZ9AIIHrFoH0NLPPFSXKte0tgrpKeKnzBG+Gl3/AH2RufK0OmDcxzseOZb+Uxortd6xTXX1\nlrnxRt+n27dr2m005opnl9MxEzGfpPL7CwMRXmlt1JUV1bM2npKGJ81RO/3WRsGZOQ2udzBozJJA\nAJIWetO0R/xnc2VOerCeHal3BWZfp4gvFM8sdUvz2T2mlkBDANkkzC7NzWALKQDP3L7NU3atGLbx\nA+CeaF0OHLVUZarRa5ci6aVg2NudUA18h2uYzRHnscFtNCiAiIgIiICIiAiIgIiICIiAiIgIiICI\niAiIg8jup4JZe6RjI53UVyt0orLNdIhnLQV0YOiTSdksDgSySJ2bXscQRmAR0blGNnXWKppK2JtH\nfLHIymvlua/UIZnN1w1MDj8Sinjyljd0OIzJaV7Va83V8I1T5oMQWRjRiCyxPjjicWsZd7eXb5PZ\n6l52Br3DVHI74cgadgLig2Gi8/ue4upL5b4bhSa2tl1Rz007dFTR1UR01FHVRHbFUxyZtc39gRmC\nCfQIPBbsu6XT4dp4nOi4TWVhcKWlDtDdLMtc0z8jojGoDIDNxOQ2Bxbpmx+kvcWzg1tDSSUznDWy\nkE0M7Gk7Sx8r3teQNuRAz6Wp6ZNqnbcaGtIcaaajFMx+RLWTQzTSvYTyNJZM0jPl0u6pWh1Vtw3D\nUW9RNNM4iG+fB/g/ZtXs1F69RFdVyJzOZ5c5jEYnlj3z7PobYLtBXUsFZTP3yCsjbLE/LIlrhyOB\n2tcDmCDyEELOWv8A0eLXPR4ct8VQ0skeJpxG4ZOZHPPJLECOYlj2uyO0a1sBWSxXNdumqqOcxDSm\n6aa3pdbdsWqs001VRE94iZiJERF6sEREQEREBERAREQEREBddR7j/wCLvsV2LrqPcf8Axd9ighkR\nEEvQ/Db8j9yvO7qOOqDDlrqLrcXuEFNk1kcYDpqid+Yip4WkgOkcQeUgABziQGkj0VD8NvyP3KrR\n/wARe2VM2HrfURNc6noLo11XpzIjE0EsUMrxyBu+HRmeeZo/qQWdXDuQrlcO5Cgg0REEpbfhj5lZ\nD3AAkkANBLiTkABtJJPIMl5/EOJqKz22ouVxnbT0lE1z5ZHcp25MjjbyySucQ1rBtJcAF88fSC9I\nK7YpmlgjkkoLKHkQW2J+l0zBsElfIz48h5dHuN2AAka3BdLHHpI4PtTnRS3RtbM3PVBa43Vu0bC0\nzR/8uHZ7MjIFo6q3eNzOWq39+G7lqz1FzKamZCXbCc6WOsERGY5NOXL0qnCL4rtUXPniJ9WVpddq\ndJMzp7lVGevDMxn1w+nO516QWDLkIqWjuUNC8NZHDRV0JtwaCdEcUTpAKdxzyAYx5O0bFtxu3aNo\nO0EchHSF8aluLcZ9Ia/4cgloYqgVVDLE6Onirtc4t0jm6GT0mZzDGHJ28Z6HZHY0uLl9saZmZzK7\ne6Tcam/XA4VtUpipowx+L7pE46qSilGbLRTEclwq2agXZ5xRZuycXADZ1nt0FHTw0lLEyCmpImQ0\n8ETdLIoo2hrGNHQAAvJbh9ptVLZKV9oqOHU9y1V890cdVRcqypOqqrat59o1LpAQ5rtrNAZs0ZD2\n6PwREQEREBERAREQEREBERAREQEREBERAREQEREBERBqfdAttTh64vxRbI3y0FSAMXWiBhe6eFg0\nsvVFG3kr4G/Eb/7sTTyOYCtl0N2pZ6WOuhqIpKOeFtRHVtkbvDoHtD2yiQ+yGaTnmV5/da3Qbbhm\n2S3K5Pyjb+nBTs0merncDop4GOI1PIBJJ2Na1xOQC+Y2Nt0CuuInpYnvobM+sqaulsFLUS+r6Q1M\nu/FkcTjk5of7QGQa1z3ljWBxagv5ukbvmAmRSUVfcae5skA109FBJcIzkdjmzwNMIeDtBDwRlmFq\nvDW6tuVU1U2ZlLWsdE8GN9ZS1VRAw8zxEZH6gMs/aaT0KlCLyrsW654qqYmY+jO026a3S26rVi7V\nTTV1iKpiJ9YiX1kwFupYev2QtV2paqVzS4Uu+bzVho5SaScNmAHTpyXsV8bqeZ8b2SRvdHJE5r45\nI3Fr2PaQ5r2Obta4EAgjkyVtfRi9KiohmhtGKJ9+pZdEVJe5T+vTPJ0tbcJCf1qc7P1z7TCM3lzS\nXM9WCu4i4aQQCDmCMwRtBB5CDzhcoCIiAiIgIiICIiAiIgLrqPcf/F32K7F11HuP/i77FBDIijsT\n32ktlHUXCumbT0lDGZZ5n5kNaNgDWt9p73OIa1jQS5zgACSg9RQ/Db8j9ytb7pu7Dg23x1FDeLpR\nTiVj4Kq3RsdcHOa8ZPhqIKZr9GYPuyZcqq7umbs15xTnDTSz2awHNsdLC8R19wjJ9+snYTvcRGf6\nTDpyJB17HLw1ttNNTDKGFjNmWoNzefm93tH+5UVqt3s2KuGn90/95tgbB8O9x3W1F+7MWqJ6ZjMz\nHeKeXL1mPbm+lK4dyFcrh3IVKtfoNEX5lkDGuedoja5xH7NBJ+yCjnp1bpclwurbBTyEUNhIdUta\nTlPcZG5vc/mcIo3iMDmc6blzGVbFnYhukldWVVbN8WvqZ6qXbn+pUSulftPL7TysFARWv9Gn0brR\nc6Wlrb/XslkvlM+ptFqt1Y0SClhdG2epqZGAnfGySMjMbdkZOTiXu0M196Km5rbMR4lrbZcmSupK\nWhrKiNsE5ieJIaulhjzeASRomfsQaRRb03ebHhC30IittmxLa7rNKx0BxDSvpYZKdh/XLGyu1PPt\nM2gbMxyLRaC1n/D73TpKW4yYaqpS6kuzZJ7a15JEFdCx0ksbNnssmga9xzOWunZkM5HZ3pXyI3Or\ny+3Xi118ZIdb7hR1AyOWoQ1Eb3MJzHsuaC0jnDivruUBERAREQEREBERAREQEREBERAREQEREBER\nAREQECLxe7rfJLbhm+1sRLZqa2VW8PAzLJpIzFE//te9p/sg+ffpXbqD8T3+d8Umq2Wp0lHaWNOb\nHRNcBNVjIkOdNIzXqGXsNhB91aiREBFcSo3G8G26y2KvrrNiW4yXi001bVT2KOWrgp5DS0sspqNJ\nApmudO4tBzGUb9uxeA3GNy7Dd1OJcRXCSsp8KYenl4HTh4bWTscXPiinc3UdTYnQDS0gufM32gAc\nwr0i3x6Q25dZKSzWnFWGJqh1nvcrqV9LWO1y01SBMQA7aQM6aoY5ri7J0Yyc4OGWh0F/PQG3TpLr\naprHWSa6vDrY+Bvd70lsf7EUZ2kudBI3RnsAZJAOYlWaAXzS9Ce9yUWNLW1pIjuTaqhqABnqjlpp\nJGD9gKiGB3/YV9LHSsByLmg9BcAfog6KiuijcGOdk45bACcs+kjkWSQoi60bXnfGOBOXtN1Dblzj\n90ttdo9iQ+z/AEuPN+xKCVRcnbtC4QEREBERAREQF11HuP8A4u+xXYuuo9x/8XfYoIZU89KrGj7z\nejY4X/5VhxzHVzW5aay6OaToeR70ULTp08zt9zzzaRbe+XFtHS1VW/ayip56l427WwROlcNmZ5Gd\nC+d+FnSSQGpncX1FxmmrKmQ8sks8hc55y5yMj/cqO3PUTZsft6zyXLwNs9G57rTF2M0URxTHfGIi\nPefvESnI+QL9Ke3OMLS3m40tuhe2J1U52qaQEtjjjY6WV+kbXuDGOybmMzkMxnmNmYs3GaCOhuVT\nary2unsAebjSvjYNG9hzpAHsd+m4NjlyBDgTG4ZggqqW9Ldu0zXTHKHQGr3/AEGhv0aa/ViqqI8p\nmIzPDGZiMRmeUZWxXDuQrlcO5Cr45NQa6q2HfIpYxyyxyMH/AHsLf/K7VyCg+RVTA+J745Glj4nO\nZIx3K17CWuaf3BBC61uD0usCPsmJax7Yy2jvj33GieAdB395dVQg8gdHUGQaRyNfEf6gtPoLI/8A\nDxcTi2YEkhllrAMySGjhVEch0DNxPzJUP6LdjuVdf7syz4ghsFy4PUxxGakjqZK2F9QHywwCb2Y3\nNfDA4ub7YBJAIDgtDLlji0ggkFpBBByII2ggjkKC6PpIT3Ck3P2UGMaujq8ST3KN9rEO9OqGwxzN\n1Su3prRmKcVLDK1oGU0TSS4nOlq7amd8ri+R7pHuy1PkcXuOQAGbnbTkAB/ZdSDOw/QuqqulpmNL\nn1dTBAxoORc6WVsbWg8xJcAvsPlkvm76E2AX3nE9NVOaeB4cdHcah+gOaZ2PJoodvuudMwvB6Kd/\n7L6RlBwiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiIC1t6UVI6fB2ImNBJbbpZiAdPs07mTvOfQ\nGxuOXPlktkrGulDFVQT007dcNXDJBMw8jopmOjkaf2LXEIPjmuW5ZjPYM9pAzOXPkNmZXoN0jCdR\nY7tX2mqBE1tqHxaiMhLF70E7RmcmSQujkH7PC88g+hG5Ph3GVFUWCrjxXQXfCjKFnCyKalpYIqOC\nnMcMUOlmt+TGxHfdTHAxvEg2EO8rgittmJafdFwvZaimhku9ymuFoBc1kFUHMp2zSQaQS6A1FECS\n0HS2pa4Aqk7aqURmISPETzqdEHuEbnDLJxZnkTsG39guuKRzHNc1xa5hDmuaSHNcDmHNI2gg86C0\n3pG29uGcBYdwlV1EMt34fLcamKnfrbDDqrpDmSAQNVbEwEgazFKW5hpVV12VEz5HF8j3Pe7a573F\nznHpLnbSutBtX0RqV02NcPsaMy2qllO3L2YKSonee7GTlz5L6TXCimdM9zWktcRpOrmyA/ttBVO/\n+HRgV8tdX4hmYRBQxOt9C5wGT6qfQ+peznBjgDG58/Cz0FXgBQQbaOUAkjIAZnN45ByrHk27AMye\nQDaT/ZZN8qZN8EeRDdmnIHN5Oz+/yWdbaERjU72nn6N/Yf7oO22xOZGGvObuX5cns/vku5ckrhAR\nEQEREBERAXXUe4/+LvsV2LrqPcf/ABd9ig8FuqQPlsN7jjLg+W0XJjCwZuDnUcwGkc5zVCcKEGhp\nctv6LRs/bMH/AFX0Ykja9rmPAcx4LXtPI5rhk5pHQQSvnpLY5LPX3KxzEmSy1ckcTnZapaSU77Sz\nbNntxva7Zyawojebc1WIqjylsX4Z6uizutVqr+dMxHrExOPaJ9m0vRst4qMRUA4U+ldDv07HRFgk\nldFE4mBusEFrm6tQyObA8bM8xvjFsNTVWfFTKm3DD7It+njq6d8AN1EbZXE1O9s1PD97jDnDa7f9\nIJycDUainfE5ksT3RyROD45I3Fj2Pac2vY9u1rgQCCOhT+IMcXe4Qtp6241NRAzL9GSZxY4ty0uk\naNkrhlnm7MqE02tos2pomJ8/zGOf+m0t68M6jcdwt6qiumIiKY5xOY4auLNOJ4Zz0xVE46wv0uHc\nhXK4dyFXJzQg0REHj923cqpMW2Z1DO4Q1VO981trQ3N1NUacsnc7qd4ya9nOACNrWkfNfdAwbcbD\nXzW6507qeppzz7Y5Yz7k0EnJLC4cjh+4ORBA+s1FUsazInbmeYqA3RMG2TENNwS70cdXGDnE5zXs\nngef64J48pIncmek5HLIgjYg+TCKzMXovsvE92mw9cxHbbfWvobdJeGSONdNTt01r2z0sfs0rKjO\nJsgjdrMbzzbcIeh3ifPLhtmy63DK7L5f+lz/ANEFc16bc1wJc8RV8VutdM6eaUjfJCHNp6aPbqnq\npgCIYQAdp2k5NaHOIad9UfovQWu52KLEFy36hvtVNQyPtYMIgrxC6ooqd81U3N8c7Yp2ZtY1wcGg\ncuYuZgLCtmsNKKK00cdHBmHPEbHGSZ4GW+TzPzknky2anknIAcmxBGbhW5lR4UtMVupiJpiTLXVu\n9iN9VUuADnluZLYwAGtbmcg0bSSSfeLH4bH0nulOGx9J7pQZCLH4bH0nulOGx9J7pQZCLH4bH0nu\nlOGx9J7pQZCLH4bH0nulOGx9J7pQZCLH4bH0nulOGx9J7pQZCLH4bH0nulOGx9J7pQZCLH4bH0nu\nlOGx9J7pQZCLH4bH0nulOGx9J7pQZCLH4bH0nulOGx9J7pQZCLH4bH0nulOGx9J7pQZCLH4bH0nu\nlOGx9J7pQZCLH4bH0nulOGx9J7pQZCLH4bH0nulOGx9J7pQaD9MHcIOJqZlztjWi922IsEPstbcq\nYHUKdz3ZBlQwlxjcTkdbmu5WuZ89K2llglkhmjfDNA90c0MzHRyxSMcWvjkjeA5jw4EFpGYIK+w4\nrY+k90qu+6/udWjG2JpKNzDSx4et4N2u9FFGyrnuNaGG3UDpHsc2VkNOySZ2eZG/RNBbmg+fSKz+\nLvQ2vELybXdKGuh2kCqbPQ1HLsbpDZInbOfW3k5F56D0SMWOdpd6tjGrLfH15LcutlHG52n+2f7I\nNAr3u4luVXPFdwbR0LCyCMtdX3GRhNPRQk7XvOwSTEA6IQQ55B5Gtc5tkdzj0NqWN8c2ILsajTpc\n+gtUckcTiDmWPrJwJHxnkOmNjuXJwW2JrVQYMvFsq7ZAyisF8bDY7vSwscIqauDnGz3N+YLi57nS\n00kr3bd9hLtR2oNpYBwpR2O20lroI97paCIRszyL5HEl0k0rgAHTPeXPcchtceQbFOhY5rI+k90p\nw2PpPdKDK1LglY3DY+k90pw2PpPdKDIRY/DY+k90pw2PpPdKDIRY/DY+k90pw2PpPdKDIRY/DY+k\n90pw2PpPdKDIRY/DY+k90pw2PpPdKDIXXUe4/wDi77FdfDY+k90r8TVbC1wB2lpA2HlIKCNWgfSy\n3Lp69keIbTCZbnaYTHWUkYJdcLcCXuaxo9+oizc5oAzc0kDUWsat/LkFfNdEV0zTV0l7afUXNNdp\nvWpxVTOYntMPnlZLjFVQtlhdm07HNPvMdzseOZw/2I2FZy3l6Su4/Qy1lrnsX/JYjxNXOpxTRuDa\nCrjijfUVtfXQ5ExMijaC6SJpJdM3NrnO1DUGKcD4ps7iy44fq5mNJArbPGbhSvA/r/SzdA39pNJ/\nZVbV7Pdoqza5x+W+/D/xJ2/VWot6+f07keeJ4Z+sTHT0n3l9CFw7kK5XDuQq1ufkGiIgLwW7Tf6m\nCmp7VbX6bxiiY0FvcMi6li06q+5ubmDvdNTFzsx/W+Ic69457WgucQ1rAXOc4gNa0DMucTsAABOa\n1luTNN4r63FcwdvNU11sw3E8OG92inl/VrQx3uyVdUx0meWe9xQ7SCg95hSxU1roaS3UbNFNb4I4\nIGn3tLBlref6pHOzc485cTzqSTNEHlt1rDD7xZ6yihcY6vS2ptswOl0NxpHtqaKVrv6cp42Anoc7\npWRua4oZebTQ3NrdDqyAGohyIMFVGTFV07gdodHUMlZkeqvQgrWeB/8AKMSXezH2aW/A4jtAyIY2\nV5ZT3mlYTs1CcQ1GkZbKpxy5SQ2YiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgg8f4m\nhs1srLnOC5tDCXsib7887iI6enjHPJJM+OMDpeFF7j2GZbZa2CrIfc7nLLc7zMOWS41pEs7c+dkY\n0Qt/6YGqCxL/AJ5iWjtY9q3YREV3u3OyW6StcLPRO28sbN8q3NIP/sLZpKAiIgKKxjh6mu1vrLbW\nN1U9xgfBLyam6h7MjM+SRjw17TzFgUqmaDw+4viCpq6GWiuLs7vhyd1su3TNJC1ppq4DIZx1NM6K\nYHkze8cy9wtX7pB9R3mgxK06KGu3my4lA2MbDLIRarnIcwAYaqTeXOyJ0VQH9K2iUHCIiAiIgIiI\nCIiAiIgIiIC5AXC8Tu1YhnoLU6OhP+aXqeG02hvOKyudvYn2A+zDDv05OWQEG3JB07ljTeb7dMQv\n9qjtYkw9h/adDmQS67xXMB2O32sYyFrx/TRHmcts5qB3PcPQWm1UFspvgW2mjp2OIAc8xjJ8r8tm\nt79Tz+7yp5ARUC46mKewWPwdx84nHUxT2Cx+DuPnEF+9A6B9AmgdA+gVBOOpinsFj8HcfOJx1MU9\ngsfg7j5xBavdxqZK+ShwnROLKjE2t91mjyD6PD9O5ouMueR0vn1spGZjlqHnZpWybdQQU0MNPBEy\nKClijhghjaAyOKJoZHGwczWtaAB+y+dVk9KbEFLcrldhR2metvIpo5ZKinrnNp6akY5sNJSMZVNE\nNOHPkkIObnPkJJOQy9Dx1MU9gsfg7j5xBfvQOgfQJoHQPoFQTjqYp7BY/B3HzicdTFPYLH4O4+cQ\nX70DoH0C1j6Q9G6no6PEdNFrq8F1YuZbG1m+TWx7DT3mmBdkAHUMkknKPap2KqXHUxT2Cx+DuPnF\n+Kj0zsTyMfHJbrE+OVrmSMdR3Etcx4LXNI4ZtBBI/ugvxQ1ENRFFPC5kkNTGyaGVmRbJHI0Pje08\n7S1wP913aB0D6BfOnAnpX4ks9upbZT0tqmp7ewxU76ynrpJmwh7nRQl8dUwOZGwtjbmM9Mbcy45k\nzfHUxT2Cx+DuPnEF+9A6B9AmgdA+gVBOOpinsFj8HcfOJx1MU9gsfg7j5xBfvQOgfQJoHQPoFQTj\nqYp7BY/B3HzicdTFPYLH4O4+cQX70DoH0CaB0D6BUE46mKewWPwdx84nHUxT2Cx+DuPnEF+9A6B9\nAmgdA+gVBOOpinsFj8HcfOJx1MU9gsfg7j5xBfvQOgfQJoHQPoFQTjqYp7BY/B3HzicdTFPYLH4O\n4+cQX70DoH0CaB0D6BUE46mKewWPwdx84nHUxT2Cx+DuPnEF+9A6B9AmgdA+gVBOOpinsFj8HcfO\nJx1MU9gsfg7j5xBfvQOgfQJoHQPoFQTjqYp7BY/B3HzicdTFPYLH4O4+cQX70DoH0CaB0D6BUE46\nmKewWPwdx84nHUxT2Cx+DuPnEF+9A6B9AmgdA+gVBOOpinsFj8HcfOJx1MU9gsfg7j5xBfvQOgfQ\nJoHQPoFQTjqYp7BY/B3HzicdTFPYLH4O4+cQX70DoH0Cg8f4lprLa6661QzhttO+dzG6Q+V4GUUE\nerZvkkpZG3PneFSDjqYp7BY/B3Hzi8/jP0p8QXbgAq6O071a6+C4tpoqeubDUz0weadtW01RdLAy\nRwkDAWgvjYTnlkgvHuI4WnttrD6/J13vc8t2vcm0/wDP1mT3wt1E6YoYxFA1oOQEGzlXuNA6B9Aq\nCcdTFPYLH4O4+cTjqYp7BY/B3HziC/egdA+gTQOgfQKgnHUxT2Cx+DuPnE46mKewWPwdx84gv3oH\nQPoE0DoH0CoJx1MU9gsfg7j5xOOpinsFj8HcfOIL24islNcKOqoKuISU1wglp6iPIDVHKwsdkf6X\nZHMHmIB5l4bcGu05paqxXF++XXCEzbdUSyZa6yhLNdpuW0uc4TUgaHOcczJDNmql8dTFPYLH4O4+\ncXn5/SnxC68Q3ttHaYqyKikt8zIqatEFZTPkbNE2qY6pLnuilDnMc1zSN9kB1A5IPo3oHQPoE0Do\nH0CoJx1MU9gsfg7j5xOOpinsFj8HcfOIL96B0D6BNA6B9AqCcdTFPYLH4O4+cTjqYp7BY/B3HziC\n/egdA+gTQOgfQKgnHUxT2Cx+DuPnE46mKewWPwdx84gv3oHQPoE0DoH0CoJx1MU9gsfg7j5xOOpi\nnsFj8HcfOIL96B0D6BNA6B9AqCcdTFPYLH4O4+cTjqYp7BY/B3HziC/egdA+gTQOgfQKgnHUxT2C\nx+DuPnE46mKewWPwdx84gv4GDoH0C1VYmi+Ytq67IOt+BmSWqh5CyW91kUcl0qBlszgpXQU2RGYd\nLP0qq7vTTxUQQKGyNJBAcKO4Zj9xnVkZ/MFQWAPSpxBZaCK30lDaJI4nTSyVFVT3CWpqZ6iV889R\nUytqmiSZ8kjiSABtAAAACD6NoqBcdTFPYLH4O4+cTjqYp7BY/B3HziCs6IiAiIgIiICIiAiIgIiI\nCIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiI\ngIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICI\niAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgI\niICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiIP//Z\n",
      "text/html": [
       "\n",
       "        <iframe\n",
       "            width=\"400\"\n",
       "            height=\"300\"\n",
       "            src=\"https://www.youtube.com/embed/g9SaX0yeneU\"\n",
       "            frameborder=\"0\"\n",
       "            allowfullscreen\n",
       "        ></iframe>\n",
       "        "
      ],
      "text/plain": [
       "<IPython.lib.display.YouTubeVideo object at 0x7f6bdfaa9a90>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%python\n",
    "\n",
    "from IPython.display import YouTubeVideo\n",
    "from calysto.display import display\n",
    "\n",
    "display(YouTubeVideo(\"g9SaX0yeneU\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Red-Black Simulation:\n",
    "\n",
    "https://www.cs.usfca.edu/~galles/visualization/RedBlack.html\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Other notes:\n",
    "\n",
    "* TreeMap - Map interface implemented by a Red-Black Tree, implements SortedSet\n",
    "  * get, put, remove, containsKey - all O(log n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.4 Non-Binary Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4.1 Two-Three (2-3) Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Children are either 2-node or 3-node\n",
    "\n",
    "<img src=\"fig-9-32.png\" />\n",
    "<img src=\"fig-9-34.png\" />\n",
    "<img src=\"twothree-bintree.png\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4.2 B-Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* n children per node\n",
    "* useful as a database with fixed \"block\" size (disk)\n",
    "* each node has between n/2 and n children\n",
    "\n",
    "If n = 200, then each node has between 100 and 200 children. Tree of height 4 could hold:\n",
    "\n",
    "$$ 100 ^ 4 $$\n",
    "\n",
    "or 100 million values."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"fig-9-48.png\" />\n",
    "<img src=\"fig-9-49.png\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4.3 B+ Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"fig-9-55.png\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4.4 One-Two-Three-Four (1-2-3-4) Tree\n",
    "\n",
    "A B-Tree with n set to 4."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"fig-9-56.png\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.4.4.1 Comparision of 2-3-4 Trees with Red-Black"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"fig-9-60.png\" />"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java 9",
   "language": "java",
   "name": "java9"
  },
  "language_info": {
   "file_extension": ".class",
   "mimetype": "application/java-vm",
   "name": "java"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}